package com.wangzemin.leetcode.num879;

import static java.lang.Math.max;

class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int jobLength = group.length;
        int maxNum = (int) 1e9 + 7;
        int[][][] dp = new int[jobLength + 1][n + 1][minProfit + 1];
        dp[0][0][0] = 1;

        int profitableSchemes = 0;
        for (int j = 0; j <= n; j++) {
            for (int i = 1; i <= jobLength; i++) {
                int curGroup = group[i - 1];
                int curProfit = profit[i - 1];

                for (int k = 0; k <= minProfit; k++) {
                    if (curGroup > j) {
                        dp[i][j][k] = dp[i - 1][j][k];
                    } else {
                        dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - curGroup][Math.max(0, k - curProfit)]) % maxNum;
                    }

                }

            }
            profitableSchemes = (profitableSchemes + dp[jobLength][j][minProfit]) % maxNum;
        }
        return profitableSchemes;
    }

//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        System.out.println(solution.profitableSchemes(5, 3, new int[]{2, 2}, new int[]{2, 3}));
//        System.out.println(solution.profitableSchemes(10, 5, new int[]{2, 3, 5}, new int[]{6, 7, 8}));
//    }
}